// https://leetcode.cn/problems/3sum/description/?envType=study-plan-v2&envId=top-100-liked
// 15. 三数之和
// 中等
// 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
// 你返回所有和为 0 且不重复的三元组。
// 注意：答案中不可以包含重复的三元组。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function (nums) {
  const res = []
  const n = nums.length

  // O(NlgN)
  // 排序数组是为了跳过重复元素 + 双指针搜索
  nums.sort((a, b) => a - b)

  // O(N^2)
  for (let i = 0; i < n; i++) {
    // 遍历每个元素，在它的后面基于双指针
    const target = -nums[i]

    // 内层基于双指针 target
    // 确保 l 为 i 下一个元素开始
    let l = i + 1
    // 确保 r 为有效坐标
    let r = n - 1
    while (l < r) {
      const sum = nums[l] + nums[r]
      if (sum > target) {
        r--
      } else if (sum < target) {
        l++
      } else {
        // 找到了解
        res.push([nums[i], nums[l], nums[r]])

        // 跳过重复元素
        while (l + 1 < r && nums[l + 1] === nums[l]) {
          l++
        }

        // 跳过重复元素
        while (r - 1 > l && nums[r - 1] === nums[r]) {
          r--
        }

        l++
        r--
      }
    }

    // 外层遍历的元素还是需要去重的
    while (i + 1 < n && nums[i] === nums[i + 1]) {
      i++
    }
  }

  return res
}

console.log(threeSum([-1, 0, 1, 2, -1, -4]))
